#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

// D指的是双向，LT指的是链表
// typedef char LTDataType;
// 以int为例，带头结点
typedef int LTDataType;
typedef struct ListNode
{
    LTDataType data;
    struct ListNode* next;
    struct ListNode* prev;
}ListNode;

// 申请一处空间，用来存放新结点
ListNode* BuyListNode(LTDataType val)
{
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = val;
    newNode->next = NULL;
    newNode->prev = NULL;

    return newNode;
}

// 初始化链表,返回指向头结点的头指针
ListNode* ListInit(void)
{
    ListNode* pHead = BuyListNode(0);
    // 在只有一个头结点的时候，头结点的prev和next指针都指向自己
    pHead->next = pHead;
    pHead->prev = pHead;

    return pHead;
}

// 销毁链表，包括头结点
void ListDestroy(ListNode* pHead)
{
    assert(pHead != NULL); // 断言

    ListNode* cur = pHead->next;
    while (cur != pHead){
        ListNode* next = cur->next;
        free(cur);
        cur = next;
    }

    free(pHead);
    pHead = NULL;
}

// 打印链表(接换行)
void ListPrint(ListNode* pHead)
{
    assert(pHead != NULL); // 断言

    ListNode* cur = pHead->next;
    if (cur == pHead){
        printf("NULL");
    }
    while (cur != pHead){
        printf("%d ", cur->data);
        cur = cur->next;
    }
    putchar('\n');
}

// 尾插
void ListPushBack(ListNode* pHead, LTDataType val)
{
    assert(pHead); // 断言

    ListNode* newNode = BuyListNode(val);
    ListNode* tail = pHead->prev;

    // 注意先后顺序
    tail->next = newNode;
    newNode->prev = tail;
    newNode->next = pHead;
    pHead->prev = newNode;

    // ListInsert(pHead, val);
}

// 头插
void ListPushFront(ListNode* pHead, LTDataType val)
{
    assert(pHead); // 断言

    ListNode* newNode = BuyListNode(val);
    ListNode* first = pHead->next;

    pHead->next = newNode;
    newNode->prev = pHead;
    newNode->next = first;
    first->prev = newNode;

    // ListInsert(pHead->next, val);
}

// 头删
void ListPopFront(ListNode* pHead)
{
    assert(pHead); // 断言
    assert(pHead->next != pHead); // 断言

    ListNode* first = pHead->next;
    ListNode* second = first->next;

    pHead->next = second;
    second->prev = pHead;

    free(first);
    first = NULL;

    // ListDelete(pHead->next);
}

// 尾删
void ListPopBack(ListNode* pHead)
{
    assert(pHead); // 断言
    assert(pHead->next != pHead); // 断言

    ListNode* tail = pHead->prev;
    ListNode* prev = tail->prev;

    prev->next = pHead;
    pHead->prev = prev;

    free(tail);
    tail = NULL;

    // ListDelete(pHead->prev);
}

// 查找pos
ListNode* ListFind(ListNode* pHead, LTDataType val)
{
    assert(pHead); // 断言

    ListNode* cur = pHead->next;
    while (cur != pHead){
        if (cur->data == val){
            return cur;
        }
        cur = cur->next;
    }

    return NULL;
}

// pos之前插入val
void ListInsert(ListNode* pos, LTDataType val)
{
    assert(pos);
    ListNode* prev = pos->prev;
    ListNode* newNode = BuyListNode(val);

    // prev newNode pos
    prev->next = newNode;
    newNode->prev = prev;
    newNode->next = pos;
    pos->prev = newNode;
}

// 删除pos位置的值
void ListDelete(ListNode* pos)
{
    assert(pos);
    ListNode* prev = pos->prev;
    ListNode* next = pos->next;

    prev->next = next;
    next->prev = prev;

    free(pos);
    pos = NULL;
}

bool isListEmpty(ListNode* pHead)
{
    if (pHead->next == pHead){
        return true;
    }
    else {
        return false;
    }
}

int ListSize(ListNode* pHead)
{
    int cnt = 0;
    ListNode* cur = pHead->next;

    while (cur != pHead){
        cnt++;
        cur = cur->next;
    }
    return cnt;
}

int main(void)
{
    // 初始化链表
    ListNode* pHead = ListInit();
    ListPrint(pHead);

    // 尾插
    ListPushBack(pHead, 1);
    ListPushBack(pHead, 3);
    ListPrint(pHead);

    // 尾删
    ListPopBack(pHead);
    ListPrint(pHead);

    // 头插
    ListPushFront(pHead, 5);
    ListPrint(pHead);

    // 头删
    ListPopFront(pHead);
    ListPrint(pHead);

    // 查找
    ListNode* pos = ListFind(pHead, 1);
    if (pos != NULL){
        printf("找到了！\n");
    }
    else {
        printf("没找到。\n");
    }

    // 删除
    ListDelete(pos);
    ListPrint(pHead);

    // 长度
    int length = ListSize(pHead);
    printf("该链表为%d元链表\n", length);

    // 判断是否为空
    int Flag = isListEmpty(pHead);
    if (Flag){
        printf("是的，链表为空\n");
    }
    else {
        printf("不是，链表不为空\n");
    }

    return 0;
}












